# 已知：数组array，由用户指定一个步长 step
# 分组的数量为step，接下来对每一组的元素进行插入排序即可
# while step >=1:
# for i =0,1,2,..,step:
# 对下标为 [i,i+step,i+2*step,...] 的元素进行插入排序
# for j = i+step,i+2*step,...,
# 确定待array[j]的插入位置k，k=j
# temp = array[j]
# m = i
# while m <= j-step:
# if temp > array[m] then m+=step
# else k=m; break;
# 找到了插入的位置k
# 把[k,k+step,..,j-step]位置上的元素整体往后移动一位
# 插入temp值：array[k] = temp
# 缩短步长： step = step / 2

def shell_sort(array, step):
    while step >= 1:
        for i in range(0, step + 1):
            # 对下标为 [i,i+step,i+2*step,...] 的元素进行插入排序
            for j in range(i + step, len(array), step):
                # 确定一下array[j]的位置
                k = j
                temp = array[j]
                # 确定k的值
                m = i
                while m <= j - step:
                    if temp > array[m]:
                        m += step
                    else:
                        k = m
                        break
                # 找到了k
                # 把[k,k+step,..,j-step]位置上的元素整体往后移动一位
                for n in range(j - step, k - step, -step):
                    array[n + step] = array[n]
                array[k] = temp
        step //= 2
    return array
